package oct2013;

import java.util.ArrayList;

public class PalindromePartitioning {
	ArrayList<ArrayList<String>> res;
	ArrayList<String> list;
	String s;
	int n;

	public ArrayList<ArrayList<String>> partition(String s) {
		res = new ArrayList<ArrayList<String>>();
		list = new ArrayList<String>();
		n = s.length();
		this.s = s;
		dfs(0);
		return res;
	}

	void dfs(int i) {
		if (i == n) {
			ArrayList<String> newList = (ArrayList<String>) list.clone();
			res.add(newList);
			return;
		}
		for (int j = i; j < n; ++j) {
			if (isPalindrome(i, j)) {
				list.add(s.substring(i, j + 1));
				dfs(j + 1);
				list.remove(list.size() - 1);
			}
		}
	}

	boolean isPalindrome(int i, int j) {
		while (i < j) {
			if (s.charAt(i++) != s.charAt(j--))
				return false;
		}
		return true;
	}

}
